package com.gframework.datastructure.trie;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;

import org.apache.commons.lang3.ArrayUtils;

/**
 * 支持通配符 "*" 的单词查找树。本类继承自 {@link SeparatorTrieTree} ，拥有其所有的特性，
 * 仅仅只是在查询操作上支持了通配符的处理。
 * <p>
 * 本类支持在设置key单词的时候，分隔符中间的某一段可以使用 "*" 通配符来表示匹配所有key值。
 * 例如，如果你存储了
 * <ul>
 * <li>user.id</li>
 * <li>user.*</li>
 * </ul>
 * 如果你要查询user.id，那么返回的就是user.id的数据。<br>
 * 如果你要查询user.name，那么返回的就是user.*的数据。<br>
 * 如果你要查询user.id.xxx，那么返回的就是user.*的数据。
 * </p>
 * <p>
 * 通配符匹配查询规则有优先级，例如如果你要查询user.car.name.a，
 * 那么匹配优先级从高到底的顺序为：
 * <ol>
 * <li>user.car.name.a</li>
 * <li>user.car.name.*</li>
 * <li>user.car.*.a</li>
 * <li>user.car.*.*</li>
 * <li>user.car.*</li>
 * <li>user.*.name.a</li>
 * <li>user.*.name.*</li>
 * <li>user.*.*.a</li>
 * <li>user.*.*.*</li>
 * <li>user.*.*</li>
 * <li>user.*</li>
 * <li>*.car.name.a</li>
 * <li>*.car.name.*</li>
 * <li>*.car.*.a</li>
 * <li>*.car.*.*</li>
 * <li>*.*.name.a</li>
 * <li>*.*.name.*</li>
 * <li>*.*.*.a</li>
 * <li>*.*.*.*</li>
 * <li>*.*.*</li>
 * <li>*.*</li>
 * <li>*</li>
 * </ol>
 * </p>
 * <p>
 * 通配符的设置必须是一个"*"，而且左右两侧必须时分隔符，或者在边界，否则将当作普通key值处理。
 * 错误的设置：
 * <ul>
 * <li>a. *.b</li>
 * <li>a.* .b</li>
 * <li>a.s*.b</li>
 * <li>*s.b</li>
 * <li>a.b.*s</li>
 * 正确的设置：
 * <li>*</li>
 * <li>*.a</li>
 * <li>a.*</li>
 * <li>a.*.b</li>
 * </ul>
 * </p>
 * 
 * @since 1.0.0
 * @author Ghwolf
 *
 * @param <T> 存储的数据类型
 * 
 * @see SeparatorTrieTree
 */
public class WildcardTrieTree<T> extends SeparatorTrieTree<T> {
	/**
	 * 通配符符号
	 */
	private static final String WILDCARD = "*";
	/**
	 * 默认的数组连接符号
	 */
	private static final String DEFAULT_ARRAY_JOIN_STRING = ".";
	/**
	 * 空的字符串数组
	 */
	private static final String[] EMPTY_STRING_ARR = ArrayUtils.EMPTY_STRING_ARRAY;

	/**
	 * 存储查询结果和通配符匹配的key信息封装类
	 * 
	 * @since 1.0.0
	 * @author Ghwolf
	 *
	 */
	public static class ProcessResult<T> {
		/**
		 * 查询的结果
		 */
		private T value ;
		/**
		 * 通配符匹配的key值
		 */
		private String[] wildcardParam ;
		
		public ProcessResult(T value,String[] wildcardParam) {
			this.value = value ;
			this.wildcardParam = wildcardParam;
		}
		/**
		 * 取得查询的结果
		 * @return 返回查询结果，没有则返回null
		 */
		public T getValue() {
			return this.value;
		}
		
		/**
		 * 取得通配符匹配的key值，除了默认的通配符外，其他都只会对应有一段key
		 * @return 返回一个数组，长度就是key中包含的通配符的数量，每一项都是其匹配的key值，没有则数组长度为0
		 */
		public String[] getWildcardParam() {
			return this.wildcardParam;
		}
	}
	
	/**
	 * 创建一个以"."进行分割的trie树.
	 */
	public WildcardTrieTree() {
		super();
	}
	
	/**
	 * 创建一个具有指定分隔符的trie树
	 * @param separator 分隔符
	 */
	public WildcardTrieTree(char separator) {
		super(separator);
	}

	@Override
	public T find(String key) {
		super.checkKey(key);
		return this.find(super.getRoot(), FastSplitUtil.fastSplit(key, super.getSeparator()), 0, null, null);
	}
	
	/**
	 * 尝试查询一个数据，并将key中包含的通配符所一一对应的key值一并解析返回.
	 * <p>
	 * 除了存在于结尾的通配符外，其他通配符只会根据分隔符匹配一段key值，
	 * 而如果是结尾的通配符，将可能会匹配多段key，如果这样，那么后面所有的key都会以 "." 作为连接符拼接然后当作一个字符串放到数组的最后。<br>
	 * 如果你想自定义连接符，可以调用 {@link #findProcessResult(String, String)} 方法。
	 * </p>
	 * @param key 要查询的key
	 * @return 返回的ProcessResult类对象一定不是null，可以取得查询结果和通配符匹配参数。但是存储的value可能为null
	 */
	public ProcessResult<T> findProcessResult(String key) {
		return this.findProcessResult(key,DEFAULT_ARRAY_JOIN_STRING);
	}
	
	/**
	 * 尝试查询一个数据，并将key中包含的通配符所一一对应的key值一并解析返回.
	 * <p>
	 * 除了存在于结尾的通配符外，其他通配符只会根据分隔符匹配一段key值，
	 * 而如果是结尾的通配符，将可能会匹配多段key，如果这样，那么后面所有的key都会以 指定连接符 作为连接符拼接然后当作一个字符串放到数组的最后。
	 * </p>
	 * @param key 要查询的key
	 * @param arrJoinStr 结尾的通配符匹配多段key时，转换为字符串使用的连接符，如果为null，则会当作空字符串处理
	 * @return 返回的ProcessResult类对象一定不是null，可以取得查询结果和通配符匹配参数。但是存储的value可能为null
	 */
	public ProcessResult<T> findProcessResult(String key,String arrJoinStr) {
		super.checkKey(key);
		if (arrJoinStr == null) {
			arrJoinStr = "";
		}
		List<String> wildcardParam = new ArrayList<>();
		T t = this.find(super.getRoot(), FastSplitUtil.fastSplit(key, super.getSeparator()), 0, wildcardParam, arrJoinStr);
		String[] wildcardParamArr ;
		if (wildcardParam.isEmpty()) {
			wildcardParamArr = EMPTY_STRING_ARR;
		} else {
			if (wildcardParam.size() != 1) {
				Collections.reverse(wildcardParam);
			}
			wildcardParamArr = wildcardParam.toArray(new String[wildcardParam.size()]);
		}
		return new ProcessResult<>(t,wildcardParamArr);
	}
	
	/**
	 * 按照优先级顺序，寻找优先级最高的参数，并返回
	 * 
	 * @param 当前操作的Node节点对象
	 * @param params 按照点分割后的参数数组
	 * @param index 参数数组索引
	 * @param wildcardParam 扩展参数存储数组，通配符匹配的字符串会存到此数组中，但是他的顺序是反的，需要调用处reverse处理
	 * @param arrJoinStr 数组链接符号
	 * @return 如果查出数据，则返回，否则返回null
	 */
	private T find(Node node,String[] params,int index,List<String> wildcardParam,String arrJoinStr) {
		if (index >= params.length) return null ;
		
		String key = params[index];
		if (!node.hasLeaf()) {
			return null ;
		}
		Map<String,Node> map = node.getLeaf();
		node = map.get(key);
		if (node != null) {
			T value = node.getValue();
			if (index == params.length - 1 && value != null) {
				// 全量值匹配
				return value ;
			} else {
				T t = this.find(node,params,index + 1,wildcardParam,arrJoinStr);
				if (t != null) return t ;
			}
		}
		node = map.get(WILDCARD);
		if (node != null) {
			T t = this.find(node,params,index + 1,wildcardParam,arrJoinStr);
			if (t != null) {
				if (wildcardParam != null) {
					wildcardParam.add(key);
				}
				return t;
			}
			t = node.getValue();
			if (t != null) {
				if (wildcardParam != null) {
					wildcardParam.add(this.arrayJoin(params, arrJoinStr, index));
				}
				// 通配符匹配
				return t ;
			}
		}
		return null ;
	}
	
	/**
	 * 数组转字符串，如果数组不存在或长度为0，则返回空字符串""
	 * @param arr 要转换的数组
	 * @param joinStr 连接字符串
	 * @param start 开始索引
	 * @return 返回转换后的字符串，不会时null
	 */
	private String arrayJoin(String[] arr,String joinStr,int start) {
		if (arr == null || arr.length == 0 || start < 0 || start >= arr.length) return "";
		StringBuilder sb = new StringBuilder((arr.length - start) * arr[0].length());
		int length = arr.length - 1;
		for (int x = start ; x < length ; x ++) {
			String str = arr[x];
			sb.append(str).append(joinStr);
		}
		sb.append(arr[length]);
		return sb.toString();
	}
	
}
